package com.csci;

import java.util.LinkedList;

public class GraphDiameterAlgorithm {

	int counter = 0;
	int extraSpace = 0;
	Graph g = null;

	public GraphDiameterAlgorithm(Graph g) {
		this.g = g;
	}

	public int BFS(Graph g, int sourceVertex) {
		
		Vertex maxVertex = null;
		counter++;
		
		for (Vertex v : g.vertex) {
			v.setColor(STATE.white);
			v.setDistance((int) Double.POSITIVE_INFINITY);
			v.setPred(-1);
			counter = counter+3;
		}

		g.vertex[sourceVertex].setColor(STATE.gray);
		g.vertex[sourceVertex].setDistance(0);
		g.vertex[sourceVertex].setPred(-1);

		counter = counter+3;
		
		LinkedList<Vertex> queue = new LinkedList<Vertex>();
		queue.addLast(g.vertex[sourceVertex]);
		counter++;
		while (!queue.isEmpty()) {
			Vertex headVertex = queue.remove();
			counter++;
			for (Integer v : g.vertex[headVertex.getId()].getEdgeListInt()) {
					counter++;
				if (g.vertex[v].getColor() == STATE.white) {
					g.vertex[v].setColor(STATE.gray);
					counter++;
					g.vertex[v].setDistance(g.vertex[headVertex.getId()].getDistance() + 1);
					counter++;
					g.vertex[v].setPred(g.vertex[headVertex.getId()].getId());
					counter++;
					queue.addLast(g.vertex[v]);
				}
			}
			g.vertex[headVertex.getId()].setColor(STATE.black);
			counter++;
			counter++;
			if (maxVertex == null) {
				maxVertex = g.vertex[headVertex.getId()];
				counter++;
				counter++;
			} else if (maxVertex.getDistance() < g.vertex[headVertex.getId()].getDistance()) {
				maxVertex = g.vertex[headVertex.getId()];
				counter++;
			}
		}
		return maxVertex.getDistance();
	}

	public int findDiameter() {
		int diameter = 0;
		extraSpace++;
		counter++;
		int i = 0;
		counter++;
		while (i < g.vertex.length) {
			int temp = BFS(g, i);
				counter++;
				counter++;
			if (diameter < temp) {
				diameter = temp;
				counter++;
			}
			//System.out.println("Current counter is " + i + " max diameter is " + diameter);
			i++;
		}
		//System.out.println("The diameter of the graph is " + diameter);
		//System.out.println("The total number of atomic operations was " + counter);
		return diameter;
	}
}
